package bit2;

public class TestKMP {
    public static void getNext(int[] next, String sub){
        next[0]=-1;
        next[1]=0;
        int i=2;
        int k=0;
        while (i<sub.length()){
            if((k == -1) || sub.charAt(k) == sub.charAt(i-1)) {
                next[i] = k+1;
                i++;
                k++;
            }else{
                k = next[k];
            }

        }
    }
    public static int KMP(String str,String sub,int pos){
        int lenStr=str.length();
        int lenSub=sub.length();
        int i=pos;
        int j=0;
        int[] next=new int[lenSub];
        getNext(next,sub);
        while (i<lenStr&&j<lenSub){
            if ((j == -1)||str.charAt(i)==sub.charAt(j)){
                i++;
                j++;
            }
            else {
                j=next[j];
            }
        }
        if(j>=lenSub){
            return i-j;
        }
        return -1;
    }
    public static void main(String[] args) {
        System.out.println(KMP("ababcabcdabcde","abcd",0));
        System.out.println(KMP("ababcabcdabcde","abcde",0));
        System.out.println(KMP("ababcabcdabcde","abcdef",0));

    }
}
